#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <memory>

using namespace std;


class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        matrixSum.resize(matrix.size());
        for (int idx = 0; idx < matrixSum.size(); idx++) {
            matrixSum[idx].resize(matrix[idx].size() + 1);
            matrixSum[idx][0] = 0;
            for (int loop = 1; loop < matrixSum[idx].size(); loop++) {
                matrixSum[idx][loop] = matrixSum[idx][loop - 1] + matrix[idx][loop - 1]; 
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int idx = row1; idx <= row2; idx++) {
            sum += matrixSum[idx][col2 + 1] - matrixSum[idx][col1];
        }
        return sum;
    }
private:
    vector<vector<int>> matrixSum;
};

int main()
{
    vector<vector<int>> matrix{
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9},
    };
    NumMatrix* obj = new NumMatrix(matrix);
    cout << obj->sumRegion(0, 1, 1, 2) << endl;
    return 0;
}